/**
 * quick_sort.c
 * @author: zt 2013-10-14
 */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define SWAP(a, b) {int temp = a; a = b; b = temp;}

void quick_sort_help(int* data, int left, int right)
{
	int leftIndex = left;
	int rightIndex = right;
	int privot = data[(left + right)/2];
	
	while(leftIndex <= rightIndex)
	{
		for(; data[leftIndex] < privot; leftIndex++)
				;
		for(; data[rightIndex] > privot; rightIndex--)
				;
		if(leftIndex <= rightIndex)
		{
			SWAP(data[leftIndex], data[rightIndex]);
			leftIndex++;
			rightIndex--;
		}
	}
	if(leftIndex < right)
	{
		quick_sort_help(data, leftIndex, right);	
	}
	
	if(rightIndex > left)
	{
		quick_sort_help(data, left, rightIndex);
	}
}

void quick_sort(int* data, int size)
{
	quick_sort_help(data, 0, size - 1);
}

int main(void)
{
	int size = 10000;
	int i;
	int* data = malloc(sizeof(int) * size);
	srand(time(NULL));
	
	freopen("output.txt", "w", stdout);
	for(i = 0; i < size; i++)
	{
		data[i] = rand() % size;	
	}
	
	quick_sort(data, size);
	
	for(i = 1; i <= size; i++)
	{
		if(i % 10 == 0)
		{
			putchar('\n');	
		}
		printf("%7d", data[i - 1]);
	}
	
	getchar();
	
	return 0;
}
